/**
 *分隔链表
 * https://leetcode.cn/problems/partition-list/
 * 给你一个链表的头节点 head 和一个特定值 x ，
 * 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 * 示例 1：
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 */
public class Solution_diy_86 {

    /**
     * 定义了单向链表的节点结构。
     * 作为公共静态内部类，方便外部访问。
     */
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 将一个链表按给定值 x 分隔，所有小于 x 的节点排在前面，
     * 大于或等于 x 的节点排在后面，同时保持两部分内部的原始相对顺序。
     *
     * @param head 原始链表的头节点
     * @param x    分隔的基准值
     * @return 分隔后新链表的头节点
     */
    public ListNode solution(ListNode head, int x) {
        // 创建两个虚拟头节点（哨兵节点）。
        // smallHead 用于连接所有小于 x 的节点。
        // largeHead 用于连接所有大于或等于 x 的节点。
        ListNode smallHead = new ListNode(0);
        ListNode largeHead = new ListNode(0);

        // 创建两个移动指针，分别指向两个新链表的当前末尾。
        ListNode small = smallHead;
        ListNode large = largeHead;
        
        // current 指针用于遍历原始链表。
        ListNode current = head;

        // 遍历整个原始链表。
        while (current != null) {
            if (current.val < x) {
                // 如果当前节点值小于 x，则将其连接到 small 链表。
                small.next = current;
                small = small.next;
            } else {
                // 如果当前节点值大于或等于 x，则将其连接到 large 链表。
                large.next = current;
                large = large.next;
            }
            // 移动到原始链表的下一个节点。
            current = current.next;
        }

        // 关键一步：将 large 链表的末尾指向 null。
        // 这可以防止当原链表最后一个节点小于 x 时，新链表产生环。
        large.next = null;

        // 将 small 链表的末尾连接到 large 链表的开头。
        // largeHead.next 是 large 链表的第一个有效节点。
        small.next = largeHead.next;

        // 返回 small 链表的真正头节点（虚拟头节点的下一个节点）。
        return smallHead.next;
    }
}